{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Visible Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: visiblePoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可见点的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个点数组 <code>points</code> 和一个表示角度的整数 <code>angle</code> ，你的位置是 <code>location</code> ，其中 <code>location = [pos<sub>x</sub>, pos<sub>y</sub>]</code> 且 <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 都表示 X-Y 平面上的整数坐标。</p>\n",
    "\n",
    "<p>最开始，你面向东方进行观测。你 <strong>不能</strong> 进行移动改变位置，但可以通过 <strong>自转</strong> 调整观测角度。换句话说，<code>pos<sub>x</sub></code> 和 <code>pos<sub>y</sub></code> 不能改变。你的视野范围的角度用 <code>angle</code> 表示， 这决定了你观测任意方向时可以多宽。设 <code>d</code> 为你逆时针自转旋转的度数，那么你的视野就是角度范围 <code>[d - angle/2, d + angle/2]</code> 所指示的那片区域。</p>\n",
    "\n",
    "<video autoplay=\"\" controls=\"\" height=\"360\" muted=\"\" style=\"max-width:100%;height:auto;\" width=\"750\"><source src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/04/angle.mp4\" type=\"video/mp4\" />Your browser does not support the video tag or this video format.</video>\n",
    "\n",
    "<p>对于每个点，如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 <strong>位于你的视野中</strong> ，那么你就可以看到它。</p>\n",
    "\n",
    "<p>同一个坐标上可以有多个点。你所在的位置也可能存在一些点，但不管你的怎么旋转，总是可以看到这些点。同时，点不会阻碍你看到其他点。</p>\n",
    "\n",
    "<p>返回你能看到的点的最大数目。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/04/89a07e9b-00ab-4967-976a-c723b2aa8656.png\" style=\"height: 300px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>在你的视野中，所有的点都清晰可见，包括你所在位置的那个点。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/04/5010bfd3-86e6-465f-ac64-e9df941d2e49.png\" style=\"height: 348px; width: 690px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,0],[2,1]], angle = 13, location = [1,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>如图所示，你只能看到两点之一。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= points.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>location.length == 2</code></li>\n",
    "\t<li><code>0 <= angle < 360</code></li>\n",
    "\t<li><code>0 <= pos<sub>x</sub>, pos<sub>y</sub>, x<sub>i</sub>, y<sub>i</sub> <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-visible-points](https://leetcode.cn/problems/maximum-number-of-visible-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-visible-points](https://leetcode.cn/problems/maximum-number-of-visible-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1],[2,2],[3,3]]\\n90\\n[1,1]', '[[2,1],[2,2],[3,4],[1,1]]\\n90\\n[1,1]', '[[1,0],[2,1]]\\n13\\n[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        addUp = 0\n",
    "        for a,b in points:\n",
    "            if a==location[0] and b==location[1]:\n",
    "                addUp += 1\n",
    "                points.remove([a, b])\n",
    "        angles = [self.calAngle(x, location) for x in points]\n",
    "        angles = sorted(angles)\n",
    "\n",
    "        i = 0\n",
    "        while angles[i] < angle:\n",
    "            angles.append(angles[i] + 360)\n",
    "            i += 1 \n",
    "        mini = angles[0]\n",
    "        maxi = mini + angle\n",
    "        res = 0\n",
    "        # print(angles)\n",
    "        while mini < 361:\n",
    "            left = bisect.bisect_left(angles, mini)\n",
    "            right = bisect.bisect_right(angles, maxi)\n",
    "            res = max(res, (right - left))\n",
    "            # print(left, right, mini, maxi)\n",
    "\n",
    "            while left < len(angles) and angles[left] <= mini:\n",
    "                left += 1\n",
    "            if left >= len(angles):\n",
    "                break\n",
    "            mini = angles[left]\n",
    "            maxi = mini + angle\n",
    "            # print(left, right, mini, maxi)\n",
    "\n",
    "        # print(res, addUp)\n",
    "        return res + addUp\n",
    "\n",
    "    def calAngle(self, point, location):\n",
    "        x, y = point\n",
    "        a, b = location\n",
    "        arctan = 0\n",
    "        if x == a:\n",
    "            arctan = 90\n",
    "            if y < b:\n",
    "                arctan = -90\n",
    "        else:\n",
    "            arctan = math.atan((y - b)/(x - a)) * (180 / math.pi)\n",
    "\n",
    "        # print(x, y, arctan)\n",
    "        if x >= a:\n",
    "            # print(x, y, (arctan + 360) % 360)\n",
    "\n",
    "            return (arctan + 360) % 360\n",
    "\n",
    "        # print(x, y, 180 - arctan)\n",
    "        return (180 + arctan)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        ans = 0\n",
    "        angles = []\n",
    "        for point in points:\n",
    "            if point == location:\n",
    "                ans += 1\n",
    "            else:\n",
    "                angles.append(math.atan2(point[1] - location[1], point[0] - location[0]) * 180 / math.pi)\n",
    "        angles.sort()\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        n = len(angles)\n",
    "        while i < n:\n",
    "            while j < len(angles) and angles[j] - angles[i] <= angle:\n",
    "                j += 1\n",
    "            res = max(res, j - i)\n",
    "            if angles[i] < 0:\n",
    "                angles.append(angles[i] + 360)\n",
    "            i += 1\n",
    "        return res + ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        p_x,p_y=location\n",
    "        result,add=[],0\n",
    "        for x,y in points:\n",
    "            if x==location[0] and y==location[1]:\n",
    "                add+=1\n",
    "            else:\n",
    "                result.append((math.atan2(y-p_y,x-p_x)*180/math.pi+360)%360)\n",
    "        result.sort()\n",
    "        ans,n=0,len(result)\n",
    "        for i,theta in enumerate(result):\n",
    "            if theta-angle<0:\n",
    "                index=bisect_left(result,theta-angle+360)\n",
    "                ans=max(ans,i+1+n-index)\n",
    "            else:\n",
    "                index=bisect_left(result,theta-angle)\n",
    "                ans=max(ans,i-index+1)\n",
    "        return ans+add\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        x, y = location\n",
    "        degrees = []\n",
    "        cnt = 0\n",
    "        for px, py in points:\n",
    "            if x == px and y == py:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            dx = px - x\n",
    "            dy = py - y\n",
    "            d = atan2(dx, dy)\n",
    "            degrees.append(d*180/pi)\n",
    "        degrees.sort()\n",
    "        degrees = degrees + [d + 360 for d in degrees] # 保证循环访问\n",
    "        n = len(degrees)\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        while True:       \n",
    "            while j < n:\n",
    "                if degrees[j] - degrees[i] <= angle:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            ans = max(ans, j-i)\n",
    "            if j == n: break\n",
    "            \n",
    "            while i < j:\n",
    "                if degrees[j] - degrees[i] > angle:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        return ans + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        sameCnt = 0\n",
    "        polarDegrees = []\n",
    "        for p in points:\n",
    "            if p == location:\n",
    "                sameCnt += 1\n",
    "            else:\n",
    "                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))\n",
    "        polarDegrees.sort()\n",
    "\n",
    "        n = len(polarDegrees)\n",
    "        polarDegrees += [deg + 2 * pi for deg in polarDegrees]\n",
    "\n",
    "        degree = angle * pi / 180\n",
    "        maxCnt = max((bisect_right(polarDegrees, polarDegrees[i] + degree) - i for i in range(n)), default=0)\n",
    "        return maxCnt + sameCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        n = len(points)\n",
    "        sameCnt = 0\n",
    "        maxCnt = 0\n",
    "        polarDegrees = []\n",
    "        angle = angle * pi / 180\n",
    "        for p in points:\n",
    "            if p == location:\n",
    "                sameCnt += 1\n",
    "            else:\n",
    "                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))\n",
    "        polarDegrees.sort()\n",
    "        polarDegrees += [deg + 2 * pi for deg in polarDegrees]\n",
    "\n",
    "        right = 0\n",
    "        for left in range(len(polarDegrees) // 2):\n",
    "            while polarDegrees[right] - polarDegrees[left] <= angle:\n",
    "                right += 1\n",
    "            maxCnt = max(maxCnt, right-left)\n",
    "        return maxCnt + sameCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math      \n",
    "class Solution:\n",
    "    def visiblePoints(self, p: List[List[int]], a: int, l: List[int]) -> int:\n",
    "        n = len(p)\n",
    "        p = [j for j in p if j !=l]\n",
    "        ans = n - len(p)\n",
    "        def f(a, b):\n",
    "            ans =  math.degrees(math.atan2(b[1]-a[1], b[0]-a[0]))\n",
    "            # if ans<0:\n",
    "            #     ans+=360 \n",
    "            return ans \n",
    "            # x1, y1 = a \n",
    "            # x2, y2 = b \n",
    "            # if y2==y1:\n",
    "            #     if x1<x2:\n",
    "            #         return 0 \n",
    "            #     else:\n",
    "            #         return 180 \n",
    "            # else:\n",
    "            #     if x1==x2:\n",
    "            #         if y1>y2:\n",
    "            #             return 270 \n",
    "            #         else:\n",
    "            #             return 90 \n",
    "            #     else:\n",
    "            #         dx = x2 - x1 \n",
    "            #         dy = y2 - y1 \n",
    "            #         t = dy/dx \n",
    "            #         z = math.degrees(math.atan(t))\n",
    "            #         if dx>0:\n",
    "            #             return z \n",
    "            #         else:\n",
    "            #             return z+180 \n",
    "        p = [f(l, j) for j in p] \n",
    "        p += [j+360 for j in p]\n",
    "        p.sort()\n",
    "        n = len(p)\n",
    "        add_ = 0 \n",
    "        # print(p)\n",
    "        # print(p)\n",
    "        for j in range(n):\n",
    "            i = bisect_right(p, p[j]+a)\n",
    "            add_ = max(add_, i-j)\n",
    "        return ans + add_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import atan, pi\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        x0, y0 = location\n",
    "        theta_list = []\n",
    "        zero_count = 0\n",
    "        max_count = 0\n",
    "        for x, y in points:\n",
    "            x -= x0\n",
    "            y -= y0\n",
    "            if x == 0 and y == 0:\n",
    "                zero_count += 1\n",
    "            elif x == 0:\n",
    "                if y > 0:\n",
    "                    theta_list.append(90.0)\n",
    "                else:\n",
    "                    theta_list.append(-90.0)\n",
    "            else:\n",
    "                theta = atan(y / x) * 180 / pi\n",
    "                if x < 0:\n",
    "                    if y < 0:\n",
    "                        theta -= 180\n",
    "                    else:\n",
    "                        theta += 180\n",
    "                theta_list.append(theta)\n",
    "        theta_list.sort()\n",
    "        theta_list.extend([x + 360 for x in theta_list])\n",
    "        left = right = 0\n",
    "        n = len(theta_list)\n",
    "        while left < n:\n",
    "            while right < n and theta_list[right] - theta_list[left] <= angle:\n",
    "                right += 1\n",
    "            max_count = max(max_count, right - left)\n",
    "            left += 1\n",
    "        return zero_count + max_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 数学问题\n",
    "    def visiblePoints1(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        self.base = 0\n",
    "        def helper(point):\n",
    "            dx, dy = point[0] - location[0], point[1] - location[1]\n",
    "            if not dx and not dy:\n",
    "                self.base += 1\n",
    "                return None\n",
    "            if not dx:\n",
    "                return 90 if dy > 0 else 270\n",
    "            if not dy:\n",
    "                return 0 if dx > 0 else 180\n",
    "            if dx * dy > 0:\n",
    "                return math.degrees(math.atan(dy/dx)) + (0 if dx > 0 else 180)\n",
    "            return math.degrees(math.atan(-dx/dy)) + (90 if dx < 0 else 270)\n",
    "        \n",
    "        angles = []\n",
    "        for p in points:\n",
    "            degree = helper(p)\n",
    "            if degree is not None:\n",
    "                angles.append(degree)\n",
    "        angles.sort()\n",
    "        angles = angles + [360 + a for a in angles]\n",
    "        l = r = ans = 0\n",
    "        while l < len(angles):\n",
    "            while r < len(angles) and angles[r] - angles[l] <= angle:\n",
    "                r += 1\n",
    "            ans = max(ans, r - l)\n",
    "            l += 1\n",
    "        return ans + self.base\n",
    "        \n",
    "    # 二分查找\n",
    "    def visiblePoints2(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        sameCnt = 0\n",
    "        polarDegrees = []\n",
    "        for p in points:\n",
    "            if p == location:\n",
    "                sameCnt += 1\n",
    "            else:\n",
    "                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))\n",
    "        polarDegrees.sort()\n",
    "\n",
    "        n = len(polarDegrees)\n",
    "        polarDegrees += [deg + 2 * pi for deg in polarDegrees]\n",
    "\n",
    "        degree = angle * pi / 180\n",
    "        maxCnt = max((bisect_right(polarDegrees, polarDegrees[i] + degree) - i for i in range(n)), default=0)\n",
    "        return maxCnt + sameCnt\n",
    "        \n",
    "    # 滑动窗口\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        sameCnt = 0\n",
    "        polarDegrees = []\n",
    "        for p in points:\n",
    "            if p == location:\n",
    "                sameCnt += 1\n",
    "            else:\n",
    "                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))\n",
    "        polarDegrees.sort()\n",
    "\n",
    "        n = len(polarDegrees)\n",
    "        polarDegrees += [deg + 2 * pi for deg in polarDegrees]\n",
    "\n",
    "        maxCnt = 0\n",
    "        right = 0\n",
    "        degree = angle * pi / 180\n",
    "        for i in range(n):\n",
    "            while right < n * 2 and polarDegrees[right] <= polarDegrees[i] + degree:\n",
    "                right += 1\n",
    "            maxCnt = max(maxCnt, right - i)\n",
    "        return sameCnt + maxCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        '''\n",
    "        如果一个点和观测点位置相同, 由于什么角度都能看见, 单独数出来\n",
    "\n",
    "        将所有点相对于观察点的角度计算出来\n",
    "        由于-179 和 180实际上夹脚很小, 为了应付这个问题, 将degrees扩充一倍, 扩充的部分都要+360度\n",
    "        这样-179就变成了181度, 和180的夹角就很小\n",
    "        '''\n",
    "        x, y = location\n",
    "        degrees = []\n",
    "        cnt = 0\n",
    "        for px, py in points:\n",
    "            if x == px and y == py:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            dx = px - x\n",
    "            dy = py - y\n",
    "            d = atan2(dx, dy)\n",
    "            degrees.append(d*180/pi)\n",
    "        degrees.sort()\n",
    "        degrees = degrees + [d + 360 for d in degrees] # 保证循环访问\n",
    "        n = len(degrees)\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        while True:       \n",
    "            while j < n:\n",
    "                if degrees[j] - degrees[i] <= angle:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            ans = max(ans, j-i)\n",
    "            if j == n: break\n",
    "            \n",
    "            while i < j:\n",
    "                if degrees[j] - degrees[i] > angle:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        return ans + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        x, y = location\n",
    "        ress = 0\n",
    "        dian = []\n",
    "        self.base = 0\n",
    "        def helper(point):\n",
    "            dx, dy = point[0] - location[0], point[1] - location[1]\n",
    "            if not dx and not dy:\n",
    "                self.base += 1\n",
    "                return None\n",
    "            if not dx:\n",
    "                return 90 if dy > 0 else 270\n",
    "            if not dy:\n",
    "                return 0 if dx > 0 else 180\n",
    "            if dx * dy > 0:\n",
    "                return math.degrees(math.atan(dy/dx)) + (0 if dx > 0 else 180)\n",
    "            return math.degrees(math.atan(-dx/dy)) + (90 if dx < 0 else 270)\n",
    "            \n",
    "        for e in points:\n",
    "            degree = helper(e)\n",
    "            if degree is not None:\n",
    "                dian.append(degree)\n",
    "        dian.sort()\n",
    "        n = len(dian)\n",
    "        dian += deepcopy(dian)\n",
    "        for i in range(n, 2*n):\n",
    "            dian[i] += 360\n",
    "        res = 0\n",
    "        right = 0\n",
    "        for left in range(n):\n",
    "            end = dian[left] + angle\n",
    "            while right < 2*n and dian[right] <= end:\n",
    "                right += 1\n",
    "            res = max(res, right - left)\n",
    "            left += 1\n",
    "        return self.base + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        x,y = location\n",
    "        polar = []\n",
    "        cnt = 0\n",
    "        for a,b in points:\n",
    "            if a==x and b==y:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            polar.append(math.atan2(b-y,a-x))\n",
    "        angle = angle * math.pi /180\n",
    "        polar.sort()\n",
    "        n = len(polar)\n",
    "        polar += [x+2*math.pi for x in polar]\n",
    "        # print(max(bisect_right(polar, angle+polar[i])-i for i in range(n)))\n",
    "        if len(polar)==0:\n",
    "            return cnt\n",
    "        return cnt+max(bisect_right(polar, angle+polar[i])-i for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        # 首先计算出观测每个点的角度，排序，然后遍历一轮不就行了？\n",
    "        angle_li = []\n",
    "        n = len(points)\n",
    "        same = 0\n",
    "        for i in range(n):\n",
    "            if points[i] == location:\n",
    "                same += 1\n",
    "                continue\n",
    "            angle_li.append(math.degrees(math.atan2(points[i][1] - location[1], points[i][0] - location[0])))\n",
    "        angle_li.sort()\n",
    "        angle_li += [a + 360 for a in angle_li]\n",
    "        # return angle\n",
    "        res, i = 0, 0\n",
    "        for j, a in enumerate(angle_li):\n",
    "            while angle_li[i] < a - angle:\n",
    "                i += 1\n",
    "            res = max(res, j-i+1)\n",
    "        return res + same\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def calculate_polar_angle(x, y):\n",
    "    # 计算极角（以弧度为单位）\n",
    "    angle_rad = math.atan2(y, x)\n",
    "\n",
    "    # 转换为以度为单位的角度\n",
    "    angle_deg = math.degrees(angle_rad)\n",
    "\n",
    "    res = angle_deg\n",
    "    if res < 0:\n",
    "        res = 360+res\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "\n",
    "        n = len(points)\n",
    "        points = [[ls[0]-location[0], ls[1]-location[1]] for ls in points if ls != location]\n",
    "        cnt = n - len(points)\n",
    "        n = len(points)\n",
    "        lst = [calculate_polar_angle(x, y) for x, y in points]\n",
    "        lst.sort()\n",
    "        lst = lst+[360+x for x in lst]\n",
    "        n = len(lst)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j<n and lst[j]-lst[i] <= angle:\n",
    "                j += 1\n",
    "            if j- i>ans:\n",
    "                ans = j-i\n",
    "        if ans > n//2:\n",
    "            ans = n//2\n",
    "        return ans + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        # location => (0, 0)\n",
    "        points = list(map(lambda P: (P[0] - location[0], P[1] - location[1]), points))\n",
    "        n = len(points)\n",
    "        points = [[x, y] for x, y in points if not (x == 0 and y == 0)]\n",
    "        cnt = n - len(points)\n",
    "        def f(P):\n",
    "            ret = math.atan2(P[1], P[0]) * 180 / math.pi\n",
    "            return 360 + ret if ret < 0 else ret\n",
    "        theta = sorted(list(map(f, points)))\n",
    "        theta += [x + 360 for x in theta]\n",
    "        m = len(theta)\n",
    "        L, R = 0, 0\n",
    "        ret = 0\n",
    "        while R < m: \n",
    "            if theta[R] - theta[L] <= angle:\n",
    "                #if R - L + 1 > ret: print(theta[L:R+1])\n",
    "                ret = max(ret, R - L + 1)\n",
    "                R += 1\n",
    "            else:\n",
    "                L += 1\n",
    "        return ret + cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import atan,pi\n",
    "deg=180/pi\n",
    "class Solution:\n",
    "    def calcRange(self,half_angle,location,target_point):\n",
    "        if target_point[0]==location[0] and target_point[1]==location[1]:\n",
    "            return -1e5,1e5\n",
    "        denominator=target_point[0]-location[0]\n",
    "        numerator=target_point[1]-location[1]\n",
    "        target_rad=atan(numerator/denominator)*deg if denominator else (90 if numerator>0 else -90)\n",
    "        xs,ys=target_point[0]<location[0],target_point[1]<location[1]\n",
    "        if xs:\n",
    "            if ys: target_rad-=180\n",
    "            else:  target_rad+=180\n",
    "        return target_rad-half_angle,target_rad+half_angle\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        half_angle=angle/2\n",
    "        balloons=[]\n",
    "        for p in points:\n",
    "            x,y=self.calcRange(half_angle,location,p)\n",
    "            balloons.append((x,y))\n",
    "            if y==1e5: continue\n",
    "            balloons.append((x+360,y+360))\n",
    "            # balloons.append((x-360,y-360))\n",
    "        balloons.sort(key=lambda p:-p[1])\n",
    "        pq=[]\n",
    "        res=0\n",
    "        for s,e in balloons:\n",
    "            while pq and -pq[0]>e: heappop(pq)\n",
    "            heappush(pq,-s)\n",
    "            res=max(res,len(pq))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import atan2, pi\r\n",
    "\r\n",
    "class Ray:\r\n",
    "    def __init__(self, dx: int, dy: int) -> None:\r\n",
    "        self.ang = atan2(dy, dx)\r\n",
    "        if self.ang < 0: self.ang += 2 * pi\r\n",
    "\r\n",
    "    def __lt__(self, other) -> bool:\r\n",
    "        return self.ang < other.ang\r\n",
    "    \r\n",
    "    def __sub__(self, other) -> float:\r\n",
    "        return self.ang - other.ang\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\r\n",
    "        cnt = 0\r\n",
    "        res = 0\r\n",
    "        arr = list()\r\n",
    "        for x, y in points:\r\n",
    "            if x == location[0] and y == location[1]:\r\n",
    "                cnt += 1\r\n",
    "            else:\r\n",
    "                arr.append(Ray(x - location[0], y - location[1]))\r\n",
    "                arr.append(Ray(x - location[0], y - location[1]))\r\n",
    "                arr[-1].ang += 2 * pi\r\n",
    "        \r\n",
    "        ang = pi * angle / 180\r\n",
    "        arr.sort()\r\n",
    "        n = len(arr)\r\n",
    "        j = 0\r\n",
    "\r\n",
    "        for i in range(n):\r\n",
    "            while arr[i] - arr[j] > ang:\r\n",
    "                j += 1\r\n",
    "            res = max(res, i - j + 1)\r\n",
    "\r\n",
    "        return res + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import atan,pi\n",
    "deg=180/pi\n",
    "class Solution:\n",
    "    def calcRange(self,half_angle,location,target_point):\n",
    "        if target_point[0]==location[0] and target_point[1]==location[1]:\n",
    "            return -1e5,1e5\n",
    "        denominator=target_point[0]-location[0]\n",
    "        numerator=target_point[1]-location[1]\n",
    "        target_rad=atan(numerator/denominator)*deg if denominator else (90 if numerator>0 else -90)\n",
    "        xs,ys=target_point[0]<location[0],target_point[1]<location[1]\n",
    "        if xs:\n",
    "            if ys: target_rad-=180\n",
    "            else:  target_rad+=180\n",
    "        return target_rad-half_angle,target_rad+half_angle\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        half_angle=angle/2\n",
    "        balloons=[]\n",
    "        for p in points:\n",
    "            x,y=self.calcRange(half_angle,location,p)\n",
    "            balloons.append((x,y))\n",
    "            if y==1e5: continue\n",
    "            balloons.append((x+360,y+360))\n",
    "            balloons.append((x-360,y-360))\n",
    "        balloons.sort(key=lambda p:p[1],reverse=True)\n",
    "        pq=[]\n",
    "        res=0\n",
    "        for s,e in balloons:\n",
    "            while pq and -pq[0]>e: heappop(pq)\n",
    "            heappush(pq,-s)\n",
    "            res=max(res,len(pq))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import atan,pi\n",
    "class Solution:\n",
    "    def calcRange(self,angle,location,target_point):\n",
    "        if target_point[0]==location[0] and target_point[1]==location[1]:\n",
    "            return -1e5,1e5\n",
    "        denominator=target_point[0]-location[0]\n",
    "        numerator=target_point[1]-location[1]\n",
    "        target_rad=atan(numerator/denominator)*180/pi if denominator else (90 if numerator>0 else -90)\n",
    "        xs,ys=target_point[0]<location[0],target_point[1]<location[1]\n",
    "        if xs and ys:     target_rad-=180\n",
    "        if xs and not ys: target_rad+=180\n",
    "        return target_rad-angle/2,target_rad+angle/2\n",
    "    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:\n",
    "        balloons=[]\n",
    "        for p in points:\n",
    "            rg=self.calcRange(angle,location,p)\n",
    "            balloons.append(rg)\n",
    "            if rg[1]==1e5: continue\n",
    "            balloons.append((rg[0]+360,rg[1]+360))\n",
    "            balloons.append((rg[0]-360,rg[1]-360))\n",
    "        balloons.sort(key=lambda p:-p[1])\n",
    "        pq=[]\n",
    "        res=0\n",
    "        for s,e in balloons:\n",
    "            while pq and -pq[0]>e: heappop(pq)\n",
    "            heappush(pq,-s)\n",
    "            res=max(res,len(pq))\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
